The statements in this section merely provide background information related to the present disclosure and may not constitute prior art.
Image segmentation is a branch of digital image processing that performs the task of categorizing, or classifying, the elements of a digital image into one or more class types. The class types can correspond to objects within an image. Classifying elements in a digital image has permitted a new understanding of biology, physiology, anatomy, as well as facilitated studies of complex disease processes and medical diagnostic purposes in clinical care settings. Modern medicine and clinical care are particularly poised to benefit from greater imaging capabilities.
Initial volumetric images from may be provided from known imaging devices such as X-ray computed tomography (CT), magnetic resonance (MR), 3-D ultrasound, positron emission tomography (PET) and many other imaging devices. The imaging device typically provides a 3D image data set from which to perform image segmentation in typical medical imaging applications with the classification types related to anatomical structure. For example, in thoracic medical images, it is convenient to segment the image voxels into classes such as bone, lung parenchyma, soft tissue, bronchial vessels, blood vessels, etc. There are many reasons to perform such a task, such as surgical planning, treatment progress, and patient diagnosis.
Various known analytical techniques are utilized to perform image segmentation. One known technique includes analyzing 3-D medical images as sequences of 2-D image slices that form the 3-D data. This is undesirable as contextual slice-to-slice information is lacking when analyzing sequences of adjacent 2-D images. Performing the segmentation directly in the 3-D space tends to bring more consistent segmentation results, yielding object surfaces instead of sets of individual contours. 3-D image segmentation techniques—for example, techniques known by the terms region growing, level sets, fuzzy connectivity, snakes, balloons, active shape and active appearance models—are known. None of them, however, offers a segmentation solution that achieves optimal results. The desire for optimal segmentation of an organ or a region of pathology, for example, is critical in medical image segmentation.
Recently, graph-based approaches have been developed in medical image segmentation. A common theme of these graph-based approaches is the formation of a weighted graph in which each vertex is associated with an image pixel and each graph edge has a weight relative to the corresponding pixels of that edge to belong to the same object. The resulting graph is partitioned into components in a way that optimizes specified, preselected criteria of the segmentation.
For example, one known technique adaptively adjusts the segmentation criterion based on the degree of variability in the neighboring regions of the image. The method attains certain global properties, while making local decisions using the minimum weight edge between two regions in order to measure the difference between them. This approach may be made more robust in order to deal with outliers by using a quintile rather than the minimum edge weight. This solution, however, is computationally complex, making the segmentation problem Non-deterministic Polynomial-time hard (NP-hard).
Additionally, many 2-D medical image segmentation methods are based on graph searching or use dynamic programming to determine an optimal path through a 2-D graph. Attempts extending these methods to 3-D and making 3-D graph searching practical in medical imaging are known. An approach using standard graph searching principles has been applied to a transformed graph in which standard graph searching for a path was used to define a surface. While the method provided surface optimality, it was at the cost of significant computational requirements.
A third class of graph-based segmentation methods is known to utilize minimum graph cut techniques, in which a cut criterion is designed to minimize the similarity between pixels that are to be partitioned. The approach, however, was biased towards finding small components. The bias was addressed later by ratio regions, minimum ratio cycles, and ratio cuts. However, all these techniques are applicable only to 2-D settings. Considering the self-similarity of the regions and captures non-local properties of the image, a novel normalized cut criterion for image segmentation was developed. Recently, it has been shown that Eigen vector-based approximation is related to the more standard spectral partitioning methods on graphs. However, all such approaches are computationally impractical for many applications.
Recently, energy minimization frameworks that utilize minimum s-t cuts to obtain medical image segmentation. Some embodiments consider non-convex smooth priors and developed heuristic algorithms for minimizing the energy functions. Cost functions may be utilized including those employing the “Gibbs model.” Interactive segmentation algorithms for n-dimensional images based on minimum s-t cuts was further developed. In some cases, a cost function used is general enough to include both the region and boundary properties of the objects.
When applied to graphs, the minimum s-t cut produces a partition of the graph at a mathematical optimal partition of two parts. There are many algorithms that have been developed to perform the minimum s-t cut of a graph. To date, the algorithms that have proven to have the greatest execution speed for performing the minimum s-t cut involve the simulation of flow through an analogous transportation or communication network. In this analogy, the weights of the edges of the graph are considered to be maximum allowable flows. A relatively new approach to the computation of the minimum s-t cut involves the use of numerical operations. Algorithms that use numerical operations for obtaining the minimum s-t cut or an approximation to the minimum s-t cut have been developed based on the linear programming methods.
Like other graph-based approaches, the energy minimization framework utilizing s-t cuts is fairly computationally complex when utilized in medical applications. Therefore, a need exists to more efficiently execute image segmentation using an energy-based framework utilizing s-t cuts.